Arbres binaires

Introduction

Un arbre binaire est un arbre de degré 2

On donne les noms gauche et droite aux enfants d’un noeud.

Cette toponymie est importante. Si un noeud n'a qu'un enfant, il faut savoir si c'est l'enfant gauche ou droit. Cela influence par exemple les parcours.

On s’y intéresse particulièrement car ils sont

• les plus simples

• souvent aussi performant que des structures plus complexes

• à la base de la majorité des autres arbres
  • tas
  • arbre binaires de recherche
  • arbres AVL
  • arbres rouge-noir
  • arbres d’Andersson
  • …

Mise en oeuvre

Les noeuds d'un arbre binaire sont typiquement de la forme

class Noeud:
    def __init__(self,val):
        self.etiquette = val
        self.gauche = None
        self.droite = None
        
    def __str__(self): 
        return "{}".format(self.etiquette)

On peut le construire manuellement

racine   = a = Noeud('A'); a.gauche = b = Noeud('B') 
a.droite = c = Noeud('C'); b.gauche = d = Noeud('D')
b.droite = e = Noeud('E'); c.gauche = f = Noeud('F')

Pour l'affichage, il est important de pouvoir distinguer si un enfant unique est à gauche ou à droite.

C'est pourquoi pour les enfants uniques nous affichons le symbole ⌀ pour les enfants absents.

Pour simplifier la visualisation, nous ne le faisons pas pour les enfants des feuilles.

import include.helpers as h
h.afficher_arbre_binaire(racine)

Illustrons notre choix avec une fonction d'affichage indenté.

def affichage_complet(R,niveau):
    if R:
        print('\t'*niveau,R)
        for r in ( R.gauche, R.droite ):
            affichage_complet(r,niveau+1)
    else:
        print('\t'*niveau,"-")

affichage_complet(racine,0)

 A
	 B
		 D
			 -
			 -
		 E
			 -
			 -
	 C
		 F
			 -
			 -
		 -

def affichage_simplifie(R,niveau):
    if R:
        print('\t'*niveau,R)
        if R.gauche or R.droite:
            for r in ( R.gauche, R.droite ):
                affichage_simplifie(r,niveau+1)
    else:
        print('\t'*niveau,"-")

affichage_simplifie(racine,0)

 A
	 B
		 D
		 E
	 C
		 F
		 -

Parcours en profondeur

Il définit 3 ordres selon que l'on traite les éléments avant, entre ou après les 2 appels récursifs.

def parcours_pre_ordonne(R,fn):
    if R:
        fn(R)
        parcours_pre_ordonne(R.gauche)
        parcours_pre_ordonne(R.droite)

def parcours_symetrique(R,fn):
    if R:
        parcours_symetrique(R.gauche)
        fn(R)
        parcours_symetrique(R.droite)
        
def parcours_post_ordonne(R,fn):
    if R:
        parcours_post_ordonne(R.gauche)
        parcours_post_ordonne(R.droite)
        fn(R)

On peut aussi écrire un parcours en profondeur plus général prenant 3 fonctions en paramètres d'entrée

def parcours_en_profondeur(R,pre,sym,post):
    if R:
        pre(R)
        parcours_en_profondeur(R.gauche,pre,sym,post)
        sym(R)
        parcours_en_profondeur(R.droite,pre,sym,post)
        post(R)

Les parcours pré-ordonné, symétrique et post-ordonné s'écrivent alors

def no_op(R): pass

def parcours_pre_ordonne(R,fn): 
    parcours_en_profondeur(R,fn,no_op,no_op)

def parcours_symetrique(R,fn): 
    parcours_en_profondeur(R,no_op,fn,no_op)

def parcours_post_ordonne(R,fn): 
    parcours_en_profondeur(R,no_op,no_op,fn)

h.afficher_arbre_binaire(racine)

# Effectuer le parcours pré-ordonné de cet arbre

def afficher_noeud(R): print(R,end = " ")
parcours_pre_ordonne(racine, afficher_noeud)

A B D E C F 

h.afficher_arbre_binaire(racine)

# Effectuer le parcours symétrique de cet arbre

parcours_symetrique(racine, afficher_noeud)

D B E A F C 

h.afficher_arbre_binaire(racine)

# Effectuer le parcours post-ordonné de cet arbre

parcours_post_ordonne(racine, afficher_noeud)

D E B F C A 

Parcours en largeur

from queue import Queue

def parcoursEnLargeur(R):
    Q = Queue()
    Q.put(R)             
    while not Q.empty():
        n = Q.get()           
        if n:
            print(n, end=" ")
            Q.put(n.gauche) 
            Q.put(n.droite)   

h.afficher_arbre_binaire(racine)

# Effectuer le parcours en largeur de cet arbre

parcoursEnLargeur(racine)

A B C D E F 

ASD1 Notebooks on GitHub.io © Olivier Cuisenaire, 2018